Recent activity in the area of autonomous vehicle or automated vehicle operation has initiated a series of reactions that stirred the automobile industry. There is a desire for the fusion of data or information from multiple sensors in order to enhance the sensing capabilities of the host autonomous vehicles. One sensor is the lidar, which utilizes multiple laser beams to locate obstacles in its surroundings and is known for its ability to depict this information in a dense three-dimensional (3D) cloud of points. The lidar has been popular amongst academic research teams for its long range and satisfactory accuracy while recent hardware advancements that promise better performing, lower cost, and smaller scale sensors have appeared to attract the interest of the industry. Typically, the lidar is mounted on the host autonomous vehicle to provide the means to acquire a 3D representation of the surrounding environment. The challenge is to analyze it and extract meaningful information such as the number of objects, a position and a velocity of an object with respect to the vehicle, and a classification of each object such as a car, a pedestrian, a pole, etc. Similar to image processing, a first step for the analysis is the segmentation or segregation of the input data into meaningful clusters.
Prior art related to the problem of point-cloud segmentation for autonomous vehicle applications is completed in two steps. One appears to regularly utilize the concept of first removing the ground plane, and consecutively clustering the remaining points. For the first step, Himmelsbach et al. [M. Himmelsbach, F. v. Hundelshausen, and H. J. Wuensche, “Fast segmentation of 3d point-clouds for ground vehicles,” in Intelligent Vehicles Symposium (IV), 2010 IEEE, June 2010, pp. 560-565] are treating the point-cloud in cylindrical coordinates and taking advantage of the distribution of the points in order to fit line segments to the point-cloud. The segments, based on some threshold of the slope are considered to capture the ground surface. In an attempt to recognize the ground surface, Moosmann et al. [F. Moosmann, O. Pink, and C. Stiller, “Segmentation of 3d lidar data in non-flat urban environments using a local convexity criterion,” in Intelligent Vehicles Symposium, 2009 IEEE, June 2009, pp. 215-220] are creating an undirected graph and compare local changes of plane normals in order to characterize changes in the slope. Consecutively, the grouping of the remaining well separated non-ground points is usually treated as a clustering problem where appropriate well known clustering algorithms are employed. Examples include the Euclidean cluster extraction [R. B. Rusu, “Semantic 3d object maps for everyday manipulation in human living environments,” Ph.D. dissertation, Computer Science department, Technische Universitaet Muenchen, Germany, October 2009] whose implementation can be found in the point-cloud library (PCL), DBSCAN [M. Ester, H.-P. Kriegel, J. Sander, X. Xu, et al., “A density-based algorithm for discovering clusters in large spatial databases with noise.” in Kdd, vol. 96, no. 34, 1996, pp. 226-231], and MeanShift [D. Comaniciu and P. Meer, “Mean shift: A robust approach toward feature space analysis,” IEEE Transactions on pattern analysis and machine intelligence, vol. 24, no. 5, pp. 603-619, 2002]. These algorithms traverse the point-cloud in an irregular way and upon finding an unlabeled point, they assign a new label which is then propagated to neighboring unlabeled points based on some rules. Inside a three dimensional space, such irregular accessing of points can lead to exhaustive search for neighbors that slow down the whole process. Although this is necessary for unorganized point-clouds, in the targeted application the layer-based organization of the point-cloud is not exploited.